package cn.bellychang.leetcode.question141;

import java.util.HashSet;

/**
 * Given head, the head of a linked list, determine if the linked list has a cycle in it.
 *
 * There is a cycle in a linked list if there is some node in the list that can be reached again
 * by continuously following the next pointer.
 * Internally, pos is used to denote the index of the node
 * that tail's next pointer is connected to.
 *
 * Note that pos is not passed as a parameter.
 *
 * Follow up: Can you solve it using O(1) (i.e. constant) memory?
 *
 * @author ChangLiang
 * @date 2021/2/3
 */
public class Solution2 {

    // Approach 1: Hash Table

    /**
     * We go through each node one by one and
     * record each node's reference (or memory address) in a hash table.
     *
     * If the current node is null, we have reached the end of the list and it must not be cyclic.
     * If current node’s reference is in the hash table, then return true.
     * @param head
     * @return
     */

    public boolean hasCycle(ListNode head) {


        HashSet<ListNode> set = new HashSet<>();
        ListNode temp = head;
        while (temp != null) {
            if (set.contains(temp)) {
                return true;
            }
            set.add(temp);
            temp = temp.next;
        }
        return false;
    }
}
